// ----------------
// Project:
// ESA Elevator
// ----------------
//
// ----------------
// Group: 163
// 2358569: Pascal Klink
// 2649456: Lukas Kreh 
// ----------------
//
// Description:
// ----------------
// elevator square root calculation
//
// Version History:
// ----------------
// 140116:

`timescale 1ns / 1ns

module sqrt

          (input wire         CLK,
           input wire         RESET,

           input wire         NEXT,
           input wire         PREVIOUS,

	   output reg 	      DONE,
	   output reg  [31:0] SQRT);
  
/* =============================INSERT CODE HERE======================================*/ 

	//Local parameters for clarifying the meaning of the state values
	localparam	waiting = 0;
	localparam	calculating = 1;
	
	//Register for storing the current estimated square root (31-bit, since max value of 16.16 is 65535,999998 < 2^16)
	reg [31:0] 	n;
	/*
	* Registers for storing the current high and low boundaries of the estimation and the
	* precision (delta) (are in 17.16 format, because if SQRT ist FFFF.FFFF, then FFFF.FFFF + 0000.1000
	* would be to big for a 16.16 format)
	*/
	reg [32:0]	delta, high, low; 
	//Helper used for storing the square value of the current square root estimation (is in 34.32 format)
	wire [65:0]	sqr;
	//The median value of the high and low register values (in 17.16, because of same reason as above)
	wire [32:0] median;
	//Register for storing the state of the module
	reg			state;
	
	/*******************
	* Sequential Logic *
	*******************/
	
	always @ (posedge CLK) begin
		/*
		* On reset, high, low and SQRT are set to 1, delta and state are set to 0 - as if the calculation
		* of the square root of 1 has finished
		*/
		if(RESET) begin
			state						<= 0;
			n 							<= 1;
			SQRT 						<= 32'b00000000000000010000000000000000;
			delta 					<= 33'b000000000000000000000000000000000;
			high 						<= 33'b000000000000000010000000000000000;
			low 						<= 33'b000000000000000010000000000000000;
		end
		
		else begin
			case(state)
				/*
				* If either NEXT or PREVIOUS is set, then the calculation of the next or previous
				* square root is prepared (delta is set to 0.5, n is increased or decreased, high 
				* and low values are set). Note that NEXT and PREVIOUS are only recognized 
				* if the calculation of a square root has finished
				*/
				waiting: begin
					if(NEXT) begin
						if(n == 0) begin
							SQRT		<= 32'b00000000000000010000000000000000;
							n 			<= 1;
						end
						else begin
							state 	<= 1;
							delta 	<= 33'b000000000000000001000000000000000;
							high 		<= {1'b0, SQRT} + 33'b000000000000000001000000000000000;
							low 		<= {1'b0, SQRT};
							n 			<= n + 1;
						end
					end
					else if(PREVIOUS) begin
						if(n <= 1) begin
							SQRT 		<= 32'b0;
							n 			<= 0;
						end
						else begin
							state		<= 1;
							delta 	<= 33'b000000000000000001000000000000000;
							high 		<= {1'b0, SQRT};
							low 		<= {1'b0, SQRT} - 33'b000000000000000001000000000000000;
							n 			<= n - 1;
						end				
					end	
				end
				/*
				* In this state the calculation takes place. To be more precise the following steps
				* are repeated 16-times by shifting delta right after every iteration (so that the 
				* precision of a 16.16 fixed-point format is completely used):
				* 	1. Caculate median of high and low estimation (done in the combinational logic block)
				*	2. Check if the square value of the median (calculated in the combinational logic block)
				*     is greater than the square-root to be caculated
				*	3. If the square value of the median is greater than the square-root, take the median
				*	   as the new high estimation, if not take the median as the new low estimation
				*/
				calculating: begin
					if (delta > 0) begin
						//Adjust the estimation of the current square root
						SQRT 			<= median[31:0];
						//Decide if median is new high or low boundary (truncate last 16-bit (2^(-17) to 2^(-23)) since they would ruin the calculation)
						if(sqr[65:16] > {2'b0, n[31:0], 16'b0000000000000000})
							high 		<= median;
						else
							low 		<= median;
						//Adjust the precision of the estimation
						delta 		<= delta >> 1;
					end
					else begin
						state 		<= 0;
					end
				end
				default: state 	<= state;
			endcase
		end
	end
	
	/**********************
	* Combinational Logic *
	**********************/
	
	assign median = (high + low) >> 1;
	assign sqr = median * median;
	always @ (*) begin
		DONE	= (state == 0);
	end
	
/* ====================================================================================*/

endmodule 
